package com.jar.exercise.坑爹的面试题;

import lombok.EqualsAndHashCode;
import lombok.Getter;
import lombok.Setter;
import lombok.ToString;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class 判断链表是否存在环 {

    static ListNode hasRing = new ListNode(-1);

    static ListNode noneRing = new ListNode(-1);

    static {

        //--------------------------------

        ListNode first = hasRing;

        for (int i = 0; i < 6; i++) {
            final ListNode listNode = new ListNode(i);
            hasRing.next = listNode;
            hasRing = listNode;
        }

        hasRing.next = first;

        //--------------------------------

        ListNode temp = noneRing;
        for (int i = 0; i < 10; i++) {
            final ListNode listNode = new ListNode(i);
            temp.next = listNode;
            temp = listNode;
        }

    }


    public static void main(String[] args) {


        // 快慢

        fs(noneRing);
        fs(hasRing);

//        loop(noneRing);

    }

    /**
     * 遍历并记录每个节点的方式
     */
    static void loop(ListNode nodes) {
        // 有环 分别记录每个节点
        List<ListNode> hasList = new ArrayList<>();
        ListNode hashTempNode = nodes;

        // 是否已经结束
        while (hashTempNode != null) {
            if (hasList.contains(hashTempNode)) {
                System.out.println("has ring.");
                return;
            }
            hasList.add(hashTempNode);
            hashTempNode = hashTempNode.next;
        }

        System.out.println("none ring.");
    }


    /**
     * 使用 快慢游标，快游标追慢游标。
     */
    static void fs(ListNode linked) {
        ListNode fast = linked;
        ListNode low = linked;
        while (fast != null && low != null) {
            fast = fast.next;
            if (fast == null) {
                System.out.println("没有环");
                return;
            }
            fast = fast.next;
            low = low.next;
            if (low == fast) {
                System.out.println("有环");
                return;
            }
        }
        System.out.println("没有环");
    }

}

/**
 *  链表节
 */
class ListNode {

    int val;

    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }

    @Override
    public String toString() {
        return "ListNode{" +
                "val=" + val +
                '}';
    }
}
